// Copyright 2024 Tvux
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package _167

// twoSum
// 时间复杂度：O(n)
// 空间复杂度：O(1)
// 双指针
func twoSum(numbers []int, target int) []int {
	left, right := 0, len(numbers)-1
	for left < right {
		if numbers[left]+numbers[right] == target {
			return []int{left + 1, right + 1}
		} else if numbers[left]+numbers[right] > target {
			right--
		} else if numbers[left]+numbers[right] < target {
			left++
		}
	}
	return []int{}
}

// twoSum
// 时间复杂度：O(n)
// 空间复杂度：O(n)
// 没有利用到题目提到的数组有序性
//func twoSum(numbers []int, target int) []int {
//	m := make(map[int]int, len(numbers)) // key: v, val: v的下标
//	for i, v := range numbers {
//		if idx, ok := m[target-v]; ok {
//			return []int{idx + 1, i + 1}
//		} else {
//			m[v] = i
//		}
//	}
//	return []int{}
//}
